class Solution {
    int m, n;
    bool vis[11][11];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

public:
    int orangesRotting(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();

        int fresh = 0;
        vector<pair<int, int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    fresh++;
                } else if (grid[i][j] == 2) {
                    q.emplace_back(i, j);
                }
            }
        }

        int ans=0;
        while(fresh&&!q.empty())
        {
            ans++;
            vector<pair<int, int>> nxt;
            for(auto& [x,y]:q)
            {
                for(int k=0;k<4;k++)
                {
                    int i=x+dx[k],j=y+dy[k];
                    if(i>=0&&i<m&&j>=0&&j<n&&grid[i][j]==1)
                    {
                        fresh--;
                        grid[i][j]=2;
                        nxt.emplace_back(i,j);
                    }
                }
            }

             q=move(nxt);
        }

        return fresh ? -1 : ans;
    }
};



#include <vector>
#include <queue>

using namespace std;

class Solution {
    int m, n;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

public:
    int orangesRotting(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;

        int fresh = 0;

        // 第一次遍历：找出所有腐烂橘子和新鲜橘子数量
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) {
                    q.push({i, j});  // 腐烂橘子入队列
                } else if (grid[i][j] == 1) {
                    fresh++;           // 新鲜橘子计数
                }
            }
        }

        // 如果没有新鲜橘子，直接返回 0
        if (fresh == 0) return 0;

        int minutes = 0;

        // BFS 主循环
        while (!q.empty() && fresh > 0) {
            int levelSize = q.size();  // 当前层有多少个腐烂橘子
            minutes++;                 // 每一层处理就是一分钟过去

            for (int _ = 0; _ < levelSize; ++_) {
                auto [x, y] = q.front(); q.pop();

                for (int k = 0; k < 4; ++k) {
                    int i = x + dx[k];
                    int j = y + dy[k];

                    // 如果这个位置是新鲜橘子，就感染它
                    if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
                        grid[i][j] = 2;  // 变成腐烂橘子
                        fresh--;         // 新鲜橘子减少
                        q.push({i, j});  // 加入队列，下一分钟继续传播
                    }
                }
            }
        }

        // 如果还有新鲜橘子没被感染，返回 -1
        return fresh > 0 ? -1 : minutes;
    }
};